/**
 * @param {number[]} arr
 * @param {number} target
 * @return {number}
 */
var search = function (arr, target) {
  let start = 0
  let end = arr.length - 1

  var mid_search = function (start, end) {
    let mid = Math.floor((end + start) / 2)
    while (start < end) {
      mid = Math.floor((end + start) / 2)
      if (start === mid || end === mid) break
      if (arr[mid] > arr[0]) {
        start = mid
      } else if (arr[mid] === arr[0]) {
        let hasPrev = false
        let tmp = mid
        while (mid > start) {
          if (arr[mid - 1] > arr[mid]) {
            return mid - 1
          } else {
            if (arr[mid - 1] < arr[mid]) {
              hasPrev = true
            } else if (hasPrev) {
              return mid - 1
            }
            mid -= 1
          }
        }
        mid = tmp
        while (mid < end) {
          if (arr[mid + 1] == arr[mid]) {
            mid += 1
          } else {
            return arr[mid + 1] > arr[mid] ? mid + 1 : mid
          }
        }
      } else {
        end = mid
      }
    }
    return mid
  }
  var bin_search = function (left, right) {
    while (left <= right) {
      let mid = Math.floor((left + right) / 2)

      if (arr[mid] === target) {
        // 找到了目标元素，继续向左搜索第一次出现的索引
        while (arr[mid - 1] === target) {
          mid--
        }
        return mid
      } else if (arr[mid] < target) {
        left = mid + 1
      } else {
        right = mid - 1
      }
    }

    // 没有找到目标元素
    return -1
  }
  let mid = mid_search(start, end)
  let res = -1
  if (arr[0] <= target) {
    res = bin_search(0, mid)
  }
  if (res === -1) {
    res = bin_search(mid + 1, arr.length - 1)
  }
  return res
}

let arr = [15, 16, 19, 20, 25, 1, 3, 4, 5, 7, 10, 14]
let target = 5
arr = [
  1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2,
  1, 1, 1, 1, 1, 1, 1
]
target = 2

arr = [2, 1, 2, 2, 2]
target = 1
arr = [2, 2, 2, 0, 2, 2]
target = 0
console.log(search(arr, target))
